package com.atguigu.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * 快速排序：是对冒泡排序的改进。通过一次排序，将要排序的数据分割为独立的两部分，其中一部分的所有数据数据都比另外一部分的
 * 所有数据都要小，按照这种方法对这两部分数据分别进行快读排序，整个排序的过程可以递归进行，以此达到整个
 * 数据变成有序序列。
 * 规则:1）首先设置一个分界值，通过该分界值将数组分为左右狼部分。
 *      2）将大于或者等于临界值的数据数据集中到数组的右边，小于分界值的数据集中到数组的左边，此时左边的各个元素都要小于分界值，而有右边的元素都大于分界值
 *      3）左边右边都再次进行快速排序，重复进行。
 *  花费的时间：大约20ms。
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr=new int[]{-9,78,0,23,-567,70};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        int[] array = new int[8000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(800000000);
        }
        //System.out.println(Arrays.toString(array));
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        quickSort(array,0,array.length-1);
        System.out.println("排序后的时间：" + System.currentTimeMillis());

    }

    /**
     *
     * @param arr:待排序的数组
     * @param left：左下标
     * @param right：右下标
     */
    public static void quickSort(int[] arr,int left,int right){
        int l=left;
        int r=right;
        int pivot=arr[(left+right)/2];
        //临时变量在交换的时候使用
        int temp=0;
        //左边的索引小于右边的索引则继续
        while (l<r){
            //寻找到一个大于等于pivot的值，才退出，可以得到下标
            while(arr[l]<pivot){
                l+=1;
            }
            //寻找一个小于等于当前值的数，然后退出，可以得到下标
            while(arr[r]>pivot){
                r-=1;
            }
            if (l>=r){
                //说明pivot的左右两边的值已经按照左边小于等于pivot的值，右边大于等于pivot
                break;
            }
            //将数据进行交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            //交换完之后，发现arr[l]==pivot的值，r前移
            if (arr[l]==pivot){
                r-=1;
            }
            //交换之后，发现arr【r】==pivot，相等l++，后移
            if(arr[r]==pivot){
                l++;
            }
        }
        //如果l==r,必须进行l++，r--，否则会出现栈溢出
        if (l==r){
            l+=1;
            r-=1;
        }
        //向左递归，保证左有序
        if (left<r){
            quickSort(arr,left,r);
        }
        //向右递归，保证右有序
        if (right>l){
            quickSort(arr,l,right);
        }
    }
}
